Chain reduction enables reduced ordered binary decision diagrams (BDDs) andzero-suppressed binary decision diagrams (ZDDs) to each take advantage of theothers' ability to symbolically represent Boolean functions in compact form.For any Boolean function, its chain-reduced ZDD (CZDD) representation will beno larger than its ZDD representation, and at most twice the size of its BDDrepresentation. The chain-reduced BDD (CBDD) of a function will be no largerthan its BDD representation, and at most three times the size of its CZDDrepresentation. Extensions to the standard algorithms for operating on BDDs andZDDs enable them to operate on the chain-reduced versions. Experimentalevaluations on representative benchmarks for encoding word lists, solvingcombinatorial problems, and operating on digital circuits indicate that chainreduction can provide significant benefits in terms of both memory andexecution time.
展开▼
